import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2023-11-03
 * Time:8:15
 */
public class test {
    //实现一个方法 transform,以数组为参数,循环将数组中的每个元素乘以 2 ,
    //并设置到对应的数组元素上
    public static int[] transform(int[] array) {
        for (int i = 0; i < array.length; i++) {
            array[i] *= 2;
        }
        return array;
    }

    public static void main1(String[] args) {
        int[] array1 = new int[]{1, 2, 3, 4};
        transform(array1);
        for (int a : array1
        ) {
            System.out.print(a + " ");
        }
    }

    //奇数位于偶数前
    //解法一：再来一个数组，遍历2次原数组，第一次把奇数放进新数组，第二次放偶数
    public static int[] func1(int[] array) {
        int[] arr = new int[array.length];
        int count = 0;  //先记录前面有多少个奇数
        int i = 0;
        for (int j = 0; j < array.length; j++) {
            if (array[j] % 2 != 0) {
                arr[i++] = array[j];
                count++;
            }
        }
        for (int j = 0; j < arr.length; j++) {
            if (array[j] % 2 == 0) {
                arr[i++] = array[j];
            }
        }
        return arr;
    }
    //解法二：只对原数组进行操作
    //最开始标记数组首尾两个元素（i和j），i开始遍历
    public static void func2(int[] array) {
        int i = 0,j = array.length - 1;
        while(i<j) {
            while(i < j && array[i] % 2 != 0) {  //i从前向后遍历，遇到偶数时和j所处位置的元素进行交换
                i++;
            }
            while(i < j && array[j] % 2 == 0) {  //j从后向前遍历，遇到奇数时交换
                j--;
            }
            //到此处时，i停在偶数，j停在奇数
            int tmp = array[j];
            array[j] = array[i];
            array[i] = tmp;
        }
    }

    public static void main2(String[] args) {
        int[] array1 = new int[]{11,34,652,23,25,12,7,43,4};
        /**解法一
         *
         */
        //int[] array2 = func1(array1);
        //System.out.println(Arrays.toString(array2));
        /**解法二
         *
         */
        func2(array1);
        System.out.println(Arrays.toString(array1));
    }

    //给定一个有序整型数组, 实现二分查找
    //x为待查找的数
    //长度除2向上取整
    public static void FindInOrder(int[] array,int x) {
        int left = 0,right = array.length-1;  //数组的左右两端
        int flag = 0,count = 0;
        while(left <= right) {   //注意它们可以取等，因为取等的时候还要再判定一下是否等于x
            int mid = (right + left) / 2;  //得到每一次区间的中点
            if(array[mid] > x) {  //x比中值小  区间得往左边缩
                right = mid - 1;
            }
            else if(array[mid] < x) {
                left = mid + 1;
            }
            else {
                flag = 1;
                count++;
                System.out.println("找到了！"+"是第"+(mid+1)+"个元素，查找了"+count+"次");
                break;
            }
            count++;
        }
        if(flag == 0) {
            System.out.println("找不到！");
        }
    }

    public static void main3(String[] args) {
        int[] array1 = new int[]{2,5,8,15,17,20,36};
        FindInOrder(array1,36);
    }

    /**返回两数之和为target的元素的下标
     *前后包抄，前面的指针i往后遍历，当和后面的j的元素的和为target时
     * @param
     */
    public static int[] func3(int[] array,int target) {
        int i = 0,j = array.length - 1;
        int[] array1 = new int[2];  //根据题干要求，假设只返回一组，那大小就是2
        while(i < j) {
            while(i < j) {
                if (array[i] + array[j] == target) {
                    array1[0] = array[i];
                    array1[1] = array[j];
                    if(array1[0] == array1[1]) {
                        return new int[]{i};
                    }
                    return array1;  //因为假设只返回一组，所以可以直接break了
                } else {
                    i++;
                }
            }
            j--;
        }
        return array1;
    }

    public static void main4(String[] args) {
        int[] array3 = new int[]{1,3,5,6,7,9,12,15,1};
        int[] array4 = func3(array3,21);
        System.out.println(Arrays.toString(array4));
    }

    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，
     * 其余每个元素均出现两次。找出那个只出现了一次的元素。
     * @param args
     */
    //思路一：循环遍历，按位异或，最终结果就是只出现一次的数
    public static int AppearOnlyOnce(int[] array) {
        int mul = 0;  //0按位异或任何数，都会等于那个数
        for (int k = 0; k < array.length; k++) {
            mul ^= array[k];
        }
        return mul;
    }

    public static void main5(String[] args) {
        int[] array1 = new int[]{2,3,5,3,6,2,5};
        System.out.println(AppearOnlyOnce(array1));
    }

    /**
     * 找出数组中的多数元素（数组非空且必存在多数元素）
     * @param args
     */
    public static void main6(String[] args) {
        int[] array1 = new int[]{1,1,1,1,3,7,5,1,3,3,3,3,3};
    }

    /**
     * 存在连续三个奇数的数组
     * @param args
     */
    //count计数，遇到偶数则置为0,看到最后能否为3
    public static boolean func4(int[] array) {
        int count = 0; //计数器，记录连续的奇数有几个
        for (int i = 0; i < array.length; i++) {
            if(count == 3) {
                return true;
            }
            if(array[i] % 2 != 0) {

                count++;

            } else {
                count = 0;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] array1 = new int[]{1,3,6,6,8,10,12};
        System.out.println(func4(array1));
    }
}
